//============================================================================
// Name        : Deque.h
// Author      : Adam Jozwik
// Version     : 1.0
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#ifndef DEQUE_H_
#define DEQUE_H_
#include <iostream>
#include <cstdlib>
#include <sstream>
#include <ctime>

namespace utils {

class DequeException : public std::exception {
	const char* errMessage_;
public:
	DequeException(const char* errMessage):errMessage_(errMessage){}
	const char* what() const throw() { return errMessage_; }
};

template <typename Item>
class Deque {

	class Element {
	public:
		Item _item;
		Element * _prev;
		Element * _next;

		Element(Item item, Element * prev, Element * next){
			_item = item;
			_prev = prev;
			_next = next;
		}
		~Element(){}
	};

	int _size;
	Element * _first;
	Element * _last;
public:
	Deque();
	~Deque();
	bool isEmpty();
	int size();
	void addFirst(Item item);
	void addLast(Item item);
	Item removeFirst();
	Item removeLast();
	std::string toString();

	class iterator{
	friend class Deque;

	Element * ptr;
	public:
		iterator(Element& lnr) : ptr(&lnr) {}
		iterator(Element* p=nullptr) : ptr(p) {}
		iterator& operator++() { ptr=ptr->_next; return *this; }//pre
		iterator operator++(int a) { iterator retval = *this; ++*this; return retval; }//post
		iterator& operator--() { ptr=ptr->_prev; return *this; }//pre
		iterator operator--(int a) { iterator retval = *this; --*this; return retval; }//post
		Item& operator*() const { return ptr->_item; }
		bool operator==(const iterator& rhs) const { return ptr == rhs.ptr; }
		bool operator!=(const iterator& rhs) const { return ptr!=rhs.ptr; }
	};
	iterator begin() const { return iterator(_first); }
	iterator end() const { return iterator(_last==nullptr?nullptr:_last->_next); }
};

template <class Item> Deque<Item>::Deque(): _size(0), _first(nullptr), _last(nullptr) {}
template <class Item> Deque<Item>::~Deque(){
	if(_size > 0) std::cout << "delete: ";
	while(_size > 0){
		Item i = _first->_item;
		if(_size>1){
			_first = _first->_next;
			delete _first->_prev;
			_first->_prev = 0;
		} else {
			delete _first;
			_first = 0;
			_last = 0;
		}
		_size--;
		std::cout << "--" << i << " ";
	}
}
template <class Item> bool Deque<Item>::isEmpty(){
	return _size==0?true:false;
}
template <class Item> int Deque<Item>::size(){
	return _size;
}

template <class Item> void Deque<Item>::addFirst(Item item){
	//if(&item == nullptr) throw DequeException("NullPointerException");

	if(_size<1){
		_first = new Element(item, nullptr, nullptr);
		_last = _first;
		_size = 1;
	} else {
		_first = new Element(item, nullptr, _first);
		_first->_next->_prev = _first;
		_size++;
	}
	std::cout << "++" << item << " ";
}

template <class Item> void Deque<Item>::addLast(Item item){
	//if(&item == nullptr)  throw DequeException("NullPointerException");

	if(_size<1){
		_last = new Element(item, nullptr, nullptr);
		_first = _last;
		_size = 1;
	} else {
		_last = new Element(item, _last, nullptr);
		_last->_prev->_next = _last;
		_size++;
	}
	std::cout << item << "++ ";
}

template <class Item> Item Deque<Item>::removeFirst(){
	if(isEmpty()) throw DequeException("NoSuchElementException");

	Item i = _first->_item;
	if(_size>1){
		_first = _first->_next;
		delete _first->_prev;
		_first->_prev = 0;
	} else {
		delete _first;
		_first = 0;
		_last = 0;
	}
	_size--;
	std::cout << "--" << i << " ";
	return i;
}

template <class Item> Item Deque<Item>::removeLast(){
	if(isEmpty()) throw DequeException("NoSuchElementException");

	Item i = _last->_item;
	if(_size>1){
		_last = _last->_prev;
		delete _last->_next;
		_last->_next = 0;
	} else {
		delete _last;
		_first = 0;
		_last = 0;
	}
	_size--;
	std::cout << i << "-- ";
	return i;
}

template <class Item> std::string Deque<Item>::toString(){
	std::stringstream ss;
	ss << "[ ";
	for(Deque<int>::iterator ld = this->begin(); ld!=this->end(); ++ld){
		ss << *ld << " ";
	}
	ss << "]";
	return ss.str();
}
int DEQ_DEL_main() {

	try {
		Deque<int> * d = new Deque<int>();

		std::cout << "new size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
		d->addFirst(1);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
		d->addFirst(2);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
		d->addFirst(3);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
		d->addFirst(4);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
		d->addFirst(5);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
//		d->removeFirst();
//		cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << endl;
		d->addLast(1);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
//		d->removeFirst();
//		cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << endl;
//		d->removeLast();
//		cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << endl;
//		d->removeLast();
//		cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << endl;
		d->addLast(10);
		std::cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << std::endl;
//		d->removeLast();
//		cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << endl;
//		d->removeLast();
//		cout << "size: " << d->size() << " is empty: " << (d->isEmpty()==1?'Y':'N') << " " << d->toString() << endl;
		delete d;

	} catch (const std::exception& e) {
		std::cout << "Exception is: " << e.what() << std::endl;
	}

//	clock_t begin = clock();
//	clock_t end = clock();
//	double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;

	return 0;
}

} /* namespace utils */

#endif /* DEQUE_H_ */
